﻿#define _CRT_SECURE_NO_WARNINGS
#include"sort.h"

void PrintArray(int* a, int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}
void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//插入排序(插入到合适的位置，后面的依次往后移：
//如果后值小于前面连续部分值，则前值依次往后覆盖后值，后移动后值到正确位置
//时间复杂度最坏情况o(n^2)，每个元素与已排元素比较，递增数列求和,每次插入一个元素需要比较1, 2, ⋯, n − 1次
//最好情况，待排序序列已经是有序的情况下，每次插入一个元素只需要比较一次就可以确定其位置，时间复杂度为O(n)
//空间复杂度o(1)
//稳定（先遇见先移动，其余往后推）
void InsertSort(int* a, int n) {
	for (int i = 0; i < n-1; i++) {
		int tmp = i;
		int end = a[tmp + 1];
		while (tmp >= 0) {
			if (end < a[tmp]) {
				a[tmp+1] = a[tmp];
				tmp--;
			}
			else {
				break;
			}
		}
		a[tmp+1] = end;
	}
}

// 预排序  -- 目标：接近有序  gap > 1
// 插入排序  -- 目标：有序    gap == 1
// O(N^1.3)
//不稳定
void ShellSort(int* a, int n){
int gap = n;
while (gap > 1) {
	//gap /= 2;
	gap = gap / 3 + 1;

	for (int i = 0; i < n - gap; i++) {
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0) {
			if (tmp < a[end]) {
				a[end + gap] = a[end];
				end -= gap;
			}
			else {
				break;
			}
		}

		a[end + gap] = tmp;

	}

	PrintArray(a, n);
}
}

// 堆排序(由小到大排序则用大堆)
//时间复杂度o(n^logn)，最后一排向上调整
//空间复杂度o(1)
//不稳定（相同数字中，建堆先遇见的排后面，后来换根前面的被换到后面）
void AdjustDwon(int* a, int n, int root) {
	int leaf = root * 2+1;

	while (leaf <= n) {
		if (leaf + 1 <= n && a[leaf + 1] > a[leaf]) {
			leaf++;
		}
		if (a[root] < a[leaf]) {
			Swap(&a[root], &a[leaf]);
			root = leaf;
			leaf = root * 2 + 1;
		}
		else
			break;
	}
}
void HeapSort(int* a, int n) {
	//建堆要根从下往上下调
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDwon(a, n, i);
	}

	for (int j = n-1; j >= 0; j--) {
		Swap(&a[0], &a[j]);
		//根最小，其他位置不变则下调
		AdjustDwon(a, j-1, 0);
	}
}

// 选择排序（选择出最大最小：把maxi，mini，换到begin，end）
//时间复杂度o(n^2)，(递减数列求和),
//空间复杂度o(1)
//不稳定(交换位置改变相同数值的顺序，例如：3,3,1,1……）
//注意：maxi在begin上的情况
void SelectSort(int* a, int n) {
	int begin = 0;
	int end = n - 1;

	while (begin < end) {
		int maxi = begin;
		int mini = begin;
		for (int i = begin + 1; i <= end; i++) {
			if (a[maxi] < a[i]) {
				maxi = i;
			}
			if (a[mini] > a[i]) {
				mini = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		if (begin == maxi) {
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);

		begin++;
		end--;

	}

}

// 冒泡排序
//时间复杂度最坏情况o(n^2)，递减数列求和
// 最好情况o(n)
//空间复杂度o(1)
//稳定
void BubbleSort(int* a, int n) {
	for (int j = n - 1; j >= 0; j--) {
		for (int i = 0; i < j ; i++) {
			if (a[i + 1] < a[i]) {
				Swap(&a[i + 1], &a[i]);
			}
		}
	}
}

// 快速排序hoare版本
//区别传统快排减少不必要的数据交换
void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = left;
	int prev = left;
	int cur = left + 1;

	while (cur <= right)
	{//当满足a[cur] < a[keyi]时就会++prev
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		++cur;
	}//把小于k的都往前移

	Swap(&a[keyi], &a[prev]);
	keyi = prev;

	QuickSort2(a, left, keyi - 1);
	QuickSort2(a, keyi + 1, right);
}
// 快速排序挖坑法
void PartSort2(int* a, int left, int right) {
	if (left >= right)
		return;

	int begin = left, end = right;
	int key = a[left];
	while (left < right) {
		while (left < right && a[right] >= key)
			--right;
		a[left] = a[right];

		while (left < right && a[left] <= key)
			++left;
		a[right] = a[left];
	}
	a[left] = key;

	PartSort2(a, begin, left - 1);
	PartSort2(a, left+1, end);
}
// 快速排序前后指针法和hoare法相同
void PartSort3(int* a, int left, int right);

//时间复杂度o(n*logn)
//不好的情况o(n^2)
//空间复杂度o（logn），不好的情况o(n)//建栈
//不稳定
void QuickSort(int* a, int left, int right) {
	if (left >= right)
		return;

	int begin = left, end = right;
	int keyi = left;
	while (left < right) {
		while (left < right && a[right] >= a[keyi])
			--right;

		while (left < right && a[left] <= a[keyi])
			++left;
		//在交换之前l一定在r的左边
		Swap(&a[right], &a[left]);
	}
	//第二层while实现left前面都是小，right后面都是大
	// 在第一层while循环里面，left和right慢慢逼近
	// 直到两者之间有一个数或者没有数
	//跳出第一层循环一定是l和r相遇重合
	Swap(&a[keyi], &a[left]);
	keyi = left;

	QuickSort(a, begin, keyi-1);
	QuickSort(a, keyi+1, end);
}
// 快速排序 非递归实现
#include"Stack.h"
void QuickSortNonR(int* a, int left, int right) {
	ST st;
	STInit(&st);
	//注意用栈实现递归，存入栈里面的是传入递归的关键值
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st)) {
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = begin;
		left = begin;
		right = end;
		while (begin < end) {
			while (begin < end && a[end] >= a[keyi])
				--end;
			while (begin < end && a[begin] <= a[keyi])
				++begin;

			Swap(&a[begin], &a[end]);
		}
		Swap(&a[keyi], &a[begin]);
		keyi = begin;

		if (keyi + 1 < right) {
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}
		if (keyi - 1 > left) {
			STPush(&st, keyi - 1);
			STPush(&st, left);
		}
	}
	
	STDestory(&st);

}

//时间复杂度o(n*logn)
// 空间复杂度o(n)，（n+logn)
// 稳定
//归并排序
void _MergeSort(int* a, int begin, int end, int* tmp) {
	if (begin == end)
		return;

	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	int i = begin;//注意用begin
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	while (begin1 <= end1 && begin2 <= end2) {
		while (begin1 <= end1 && a[begin1] <= a[begin2]) 
			tmp[i++] = a[begin1++];
		while (begin2 <= end2 && a[begin2] <= a[begin1])
			tmp[i++] = a[begin2++];

	}

	while(begin1 <= end1)
		tmp[i++] = a[begin1++];
	while(begin2 <= end2)
		tmp[i++] = a[begin2++];

	//注意+begin
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n){
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL){
		perror("malloc fail");
		return;
	}

	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

void MergeSortNonR(int* a, int n){
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL){
		perror("malloc fail");
		return;
	}

	//一排一排的执行递归而非递归顺序
	int gap = 1;
	while (gap < n){
		for (int j = 0; j < n; j += 2 * gap){//b1到下一个b1之间的距离是e1-b1+1=2*g
			int begin1 = j, end1 = begin1 + gap - 1;//b到e一共的数是e-b+1=g
			int begin2 = begin1 + gap, end2 = begin2 + gap - 1;

			// 越界的问题处理
			if (end1 >= n || begin2 == n)//遍历到最后可以退出，排完当前序返回条件
				break;
			if (end2 >= n)
				end2 = n - 1;//缩短b2到e2的距离，保持在数组内

			int i = j;
			// 依次比较，取小的尾插tmp数组
			while (begin1 <= end1 && begin2 <= end2){
				if (a[begin1] <= a[begin2]){
					tmp[i++] = a[begin1++];
				}
				else{
					tmp[i++] = a[begin2++];
				}
			}
			while (begin1 <= end1){
				tmp[i++] = a[begin1++];
			}
			while (begin2 <= end2){
				tmp[i++] = a[begin2++];
			}

			memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));
		}

		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

// 时间复杂度：O(N+range)
// 空间复杂度：O(range)
void CountSort(int* a, int n){
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++){
		if (a[i] > max)
			max = a[i];

		if (a[i] < min)
			min = a[i];
	}

	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL){
		perror("malloc fail");
		return;
	}

	memset(count, 0, sizeof(int) * range);

	// 统计次数
	for (int i = 0; i < n; i++){
		count[a[i] - min]++;
	}

	// 排序
	int j = 0;
	for (int i = 0; i < range; i++){
		while (count[i]--){
			a[j++] = i + min;
		}
	}
}